package org.yagnus.stats.samplers.discrete.withreplacement;

import java.util.List;
import java.util.TreeMap;

import org.yagnus.datastructure.TotallyOrderedRange;
import org.yagnus.stats.samplers.discrete.Utils;

/**
 * 
 * @author Hsb
 * 
 *         This implementation of the Array sampler uses a TreeMap that maps
 *         number ranges (as implemented by TotallyOrderedRange that span the
 *         real segment [0,1] to the object corresponding to that range.
 * 
 *         Construct time: O(nlgn) to construct the tree. Draw time: O(1),
 *         O(lgn), O(n); (best, amortized, worst) Update time: When implemented,
 *         adding/removing an item should take O(lgn) on average Bulk draw:
 *         O(dlgn) Memory: O(n)
 * 
 *         Where n is the size of the population, and d is the number of draws
 *         that we make.
 * 
 *         TODO: A more sophisticated algorithm would use a Tree optimized for
 *         each distribution. TODO: write the updates to sample space
 * 
 * @param <BASETYPE>
 *            the type of stuff we're sampling from
 * 
 * 
 */
public class TreeSampler<BASETYPE> extends
		WithReplacementSampler<BASETYPE> {

	TreeMap<TotallyOrderedRange, BASETYPE> map;

	@Override
	protected void _init(List<BASETYPE> t, List<Double> weights) {

		map = new TreeMap<TotallyOrderedRange, BASETYPE>();

		if (t.size() != weights.size()) {
			throw new IllegalArgumentException(
					"The sample space and the input probability are not same length.");
		}
		List<Double> ps = Utils.makeProbability(weights, 0);

		double sum = 0, nextv;
		for (int i = 0; i < t.size(); ++i) {
			if (t.get(i) == null) {
				throw new IllegalArgumentException(
						"Sample space cannot contain null");
			}

			nextv = sum + ps.get(i);
			TotallyOrderedRange<Double> range = TotallyOrderedRange
					.getOpenRight(sum, nextv);
			map.put(range, t.get(i));
			sum = nextv;
		}

	}

	public BASETYPE draw() {
		BASETYPE ret = null;
		do {
			ret = map.get(TotallyOrderedRange.getPoint(rng().nextDouble()));
		} while (ret == null);
		return ret;
	}

	public TreeSampler(List<BASETYPE> t, List<Double> weights) {
		super(t, weights);
	}

	public TreeSampler(List<BASETYPE> t) {
		super(t);
	}

	@Override
	public void addSample(BASETYPE t, double w) {
		throw new UnsupportedOperationException("Not supported yet.");
	}

	@Override
	public void removeSample(BASETYPE t) {
		throw new UnsupportedOperationException("Not supported yet.");
	}
}
